package com.passer.labyrinth.core;


import com.passer.labyrinth.core.contant.CellType;
import com.passer.labyrinth.core.entity.Node;

import java.util.*;

public class AStarAlgorithm {

    public static List<int[]> findPath(CellType[][] maze, int[] start, int[] goal) {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Set<String> closedList = new HashSet<>();

        Node startNode = new Node(start[0], start[1], 0, heuristic(start, goal), null);
        openList.add(startNode);

        while (!openList.isEmpty()) {
            Node current = openList.poll();

            if (current.x == goal[0] && current.y == goal[1]) {
                return reconstructPath(current);
            }

            closedList.add(current.x + "," + current.y);

            for (int[] dir : new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];

                if (newX >= 0 && newX < maze.length && newY >= 0 && newY < maze[0].length && maze[newX][newY] != CellType.WALL) {
                    String pos = newX + "," + newY;
                    if (closedList.contains(pos)) continue;

                    Node neighbor = new Node(newX, newY, current.g + 1, heuristic(new int[]{newX, newY}, goal), current);
                    openList.add(neighbor);
                }
            }
        }

        return Collections.emptyList(); // 如果没有找到路径，返回空列表
    }

    // 启发式函数：曼哈顿距离
    private static int heuristic(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }

    // 回溯路径
    private static List<int[]> reconstructPath(Node node) {
        List<int[]> path = new ArrayList<>();
        while (node != null) {
            path.add(new int[]{node.x, node.y});
            node = node.parent;
        }
        Collections.reverse(path);
        return path;
    }
}